package nachos.threads;

import nachos.machine.*;

/* UNUSED DEFAULT CODE
import java.util.TreeSet;
import java.util.HashSet;
import java.util.List;
import java.util.Iterator;
import java.util.Stack;
*/
/************ START BADNACHOS CODE ************/
import java.util.LinkedList;
import java.util.ListIterator;
/************ END BADNACHOS CODE ************/


/**
 * A scheduler that chooses threads based on their priorities.
 *
 * <p>
 * A priority scheduler associates a priority with each thread. The next thread
 * to be dequeued is always a thread with priority no less than any other
 * waiting thread's priority. Like a round-robin scheduler, the thread that is
 * dequeued is, among all the threads of the same (highest) priority, the
 * thread that has been waiting longest.
 *
 * <p>
 * Essentially, a priority scheduler gives access in a round-robin fassion to
 * all the highest-priority threads, and ignores all other threads. This has
 * the potential to
 * starve a thread if there's always a thread waiting with higher priority.
 *
 * <p>
 * A priority scheduler must partially solve the priority inversion problem; in
 * particular, priority must be donated through locks, and through joins.
 */
public class PriorityScheduler extends Scheduler {
  /**
   * Allocate a new priority scheduler.
   */
  public PriorityScheduler() {
  }

  /**
   * Allocate a new priority thread queue.
   *
   * @param	transferPriority	<tt>true</tt> if this queue should
   *					transfer priority from waiting threads
   *					to the owning thread.
   * @return	a new priority thread queue.
   */
  public ThreadQueue newThreadQueue(boolean transferPriority) {
    return new PriorityQueue(transferPriority);
  }

  /**
   * getPriority()
   */
  public int getPriority(KThread thread) {
    Lib.assertTrue(Machine.interrupt().disabled());

    return getThreadState(thread).getPriority();
  }

  /**
   * getEffectivePriority()
   */
  public int getEffectivePriority(KThread thread) {
    Lib.assertTrue(Machine.interrupt().disabled());

    return getThreadState(thread).getEffectivePriority();
  }

  /**
   * setPriority()
   */
  public void setPriority(KThread thread, int priority) {
    Lib.assertTrue(Machine.interrupt().disabled());

    Lib.assertTrue(priority >= priorityMinimum && priority <= priorityMaximum);

    getThreadState(thread).setPriority(priority);
  }

  /**
   * The self test 
   */
  public static void selfTest() {
    PrioritySchedulerTest.runTest(); 
  }

  /**
   * The default priority for a new thread. Do not change this value.
   */
  public static final int priorityDefault = 1;
  /**
   * The minimum priority that a thread can have. Do not change this value.
   */
  public static final int priorityMinimum = 0;
  /**
   * The maximum priority that a thread can have. Do not change this value.
   */
  public static final int priorityMaximum = 7;    

  /**
   * Return the scheduling state of the specified thread.
   *
   * @param	thread The thread whose scheduling state to return.
   * @return The scheduling state of the specified thread.
   */
  protected ThreadState getThreadState(KThread thread) {
    if (thread.schedulingState == null) {
      thread.schedulingState = new ThreadState(thread);
    }

    return (ThreadState) thread.schedulingState;
  }
  //End of PriorityScheduler class's functions and local variables.




  /**
   * A <tt>ThreadQueue</tt> that sorts threads by priority. Only
   * parts of this are implemented and you should complete it, by adding
   * code wherever you see fit and whichever method you see fit.
   */
  protected class PriorityQueue extends ThreadQueue {
    /********** NEW CODE *********/
    /** Ordered list of KThreads ordered first by priority, then by time in the list. */
    private LinkedList<KThread> waitingThreads = new LinkedList<KThread>();
    /********** END NEW CODE ********/
    
    /***** TESTING ****/
    private ThreadState owner;
    /***** TESTING ****/
    

    PriorityQueue(boolean transferPriority) {
      this.transferPriority = transferPriority;
    }

    /**
     * The thread declares its intent to wait for access to the
     * "resource" guarded by this priority queue. This method is only called
     * if the thread cannot immediately obtain access.
     *
     * @param thread The thread 
     *
     * @see nachos.threads.ThreadQueue#waitForAccess
     */

    public void waitForAccess(KThread thread) {
      Lib.assertTrue(Machine.interrupt().disabled());
      
      
      /***** TESTING *****/
      this.waitingThreads.add(thread);
      if (this.transferPriority) {
        int newThreadsPriority = getThreadState(thread).getEffectivePriority();
        if (newThreadsPriority > this.owner.getEffectivePriority()) {
          this.owner.setEffectivePriority(newThreadsPriority);
        }
      }
      /***** TESTING *****/
      
      
      /************ NEW CODE **********/
      /*
       * Insert thread into waiting list with highest priority (lowest integer value) threads
       * first in the list, with FIFO access within the same priorities.
       * Currently no priority donation implemented.
       */
/*TESTING      int newThreadPriority = getThreadState(thread).getPriority();
      ListIterator<KThread> waitingThreadsIterator = this.waitingThreads.listIterator();
      while (waitingThreadsIterator.hasNext()) {
        if (getThreadState(waitingThreadsIterator.next()).getPriority() > newThreadPriority) {
          //Found first lower (higher number) priority thread. Reset cursor to before it.
          waitingThreadsIterator.previous();
          break;
        }
      }
      waitingThreadsIterator.add(thread);
      /************ END NEW CODE **********/
    }


    /**
     * print(): Prints the priority queue, for potential debugging 
     */
    public void print() {
      /************* NEW CODE **************/
      //Just print the waiting list.
      System.out.println(this.waitingThreads.toString());
      /************* END NEW CODE ***********/
    }

    /**
     * The specified thread has received exclusive access, without using
     * <tt>waitForAccess()</tt> or <tt>nextThread()</tt>. Assert that no
     * threads are waiting for access.
     */
    public void acquire(KThread thread) {
      Lib.assertTrue(Machine.interrupt().disabled());

      /************* NEW CODE ***********/
      //Not much actually goes on for an acquire.
      Lib.assertTrue(this.waitingThreads.size() == 0);
      /************ END NEW CODE *********/
      
      /***** TESTING ****/
      this.owner = getThreadState(thread);
      this.owner.addWaitingFor(this);
      /***** TESTING ****/
    }


    /**
     * Select the next thread in the ThreadQueue
     */
    public KThread nextThread() {
      Lib.assertTrue(Machine.interrupt().disabled());

      /***** TESTING *****/
      this.owner.removeOwnedResource(this);
      this.owner.updateEffectivePriority();
      this.owner = pickNextThread();
      this.waitingThreads.remove(this.owner);
      this.owner.addOwnedResource(this);
      this.owner.removeWaitingFor(this);
      /***** TESTING *****/

      /*********** NEW CODE ***********/
      //Get first thread in list, if there is one, and remove it from list.
/*      if (this.waitingThreads.size() > 0) {
        return this.waitingThreads.removeFirst();
      }
      else {
        return null; //DEFAULT CODE LINE
      }
      /*********** END NEW CODE *********/
    }

    /**
     * Return the next thread that <tt>nextThread()</tt> would return,
     * without modifying the state of this queue.
     *
     * @return	the next thread that <tt>nextThread()</tt> would
     *		return.
     */
    protected KThread pickNextThread() {
    
      /***** TESTING *****/
      if (this.waitingThreads.size() == 0) {
        return null;
      }
      //else
      KThread result = this.waitingThreads.getFirst();
      for (int i = 1; i < this.waitingThreads.size(); i++) {
        if (getThreadState(this.waitingThreads.get(i)).getEffectivePriority() > result) {
          result = this.waitingThreads.get(i);
        }
      }
      return result;
      /***** TESTING *****/

      /********* NEW CODE ***********/
/*TESTING      if (waitingThreads.size() > 0) {
        return this.waitingThreads.getFirst();
      }
      else {
        return null; //DEFAULT CODE LINE
      }
      /********* END NEW CODE *********/
    }

    /**
     * <tt>true</tt> if this queue should transfer priority from waiting
     * threads to the owning thread.
     */
    public boolean transferPriority;

  } // End of PriorityQueue class.



  /**
   * The scheduling state of a thread. This should include the thread's
   * priority, its effective priority, any objects it owns, and the queues
   * it's waiting for, etc. This is a convenience class so that
   * no modification to the KThread class are needed for a new scheduler.
   * Each scheduler keeps track of scheduler specific KThread information
   * in its own declaration of the ThreadState class.
   *
   * @see	nachos.threads.KThread#schedulingState
   */ 
  protected class ThreadState {

    /**
     * Allocate a new <tt>ThreadState</tt> object and associate it with the
     * specified thread.
     *
     * @param	thread	the thread this state belongs to.
     */
    public ThreadState(KThread thread) {
      this.thread = thread;
      this.priority = priorityDefault;
    }

    /**
     * Return the priority of the associated thread.
     *
     * @return	the priority of the associated thread.
     */
    public int getPriority() {
      return priority;
    }

    /**
     * Set the priority of the associated thread to the specified value.
     *
     * @param	priority	the new priority.
     */
    public void setPriority(int priority) {
      this.priority = priority;
    }

    /** The thread with which this object is associated. */	   
    protected KThread thread;
    /** The priority of the associated thread. */
    protected int priority;
    /** The effective priority of the associated thread. */
    protected int effectivePriority;


    /***** TESTING *****/

    /** Queues waiting in. **/
    //Not best structure. Can this ever be more than one anyways? 
    protected LinkedList<PriorityQueue> waitingFor = new LinkedList<PriorityQueue>();
    protected LinkedList<PriorityQueue> ownedResources = new LinkedList<PriorityQueue>();
    
    /**
     * Return the effective priority of the associated thread.
     *
     * @return	the effective priority of the associated thread.
     */
    public int getEffectivePriority() {
      return this.effectivePriority;
      
    }

    //Might need something like this. Have to think about.
    /**
     * Set the effective priority of the associated thread.
     *
     * @param effectivePriority The new effective priority.
     */
    public void updateEffectivePriority(int effectivePriority) {
      this.effectivePriority = priority;
      for (PriorityQueue q : ownedResources) {
        if (q.transferPriority) {
          this.effectivePriority = getThreadState(q.pickNextThread()).getEffectivePriority();
        }
    }
    
    public void addOwnedResource(PriorityQueue resource) {
      this.ownedResources.add(resource);
    }
    
    public void addWaitingFor(PriorityQueue resource) {
      this.waitingFor.add(resource);
    }
    public void removeOwnedResource(PriorityQueue resource) {
      this.ownedResources.remove(resource);
    }
    
    public void removeWaitingFor(PriorityQueue resource) {
      this.waitingFor.remove(resource);
    }
    
    
    /***** TESTING *****/

  } //End of ThreadState class.
} //End of Priority Scheduler class.
